package com.lsp.concurrent.locks;

import lombok.extern.slf4j.Slf4j;
import sun.misc.Unsafe;

import java.io.Serializable;
import java.lang.reflect.Field;
import java.util.concurrent.locks.AbstractOwnableSynchronizer;
import java.util.concurrent.locks.AbstractQueuedSynchronizer;
import java.util.concurrent.locks.LockSupport;

@Slf4j
public abstract class LSPAbstractQueuedSynchronizer
        extends AbstractOwnableSynchronizer
        implements Serializable {

    protected LSPAbstractQueuedSynchronizer(){}

    /**
     * AQS 中的同步队列通过链表实现、下面的静态内部内就是实现实现的载体
     */
    static final class Node {

        /**用于标记一个线程在独占模式下等待**/
        static final Node EXCLUSIVE = null;

        /**当前线程因为超时或者中断被取消、这是一个终结态，也就是线程到此为止**/
        static final int CANCELLED = 1;

        /**
         * 当前线程的后继线程被阻塞或者即将被阻塞，当前线程释放锁或者取消线程后需要幻想后继线程。
         * 这个状态一般都是后继节点来设置前驱节点的
         **/
        static final int SIGNAL = -1;

        static final int CONDITION = -2;

        /**等待状态**/
        volatile int waitStatus;

        /**前驱节点**/
        volatile Node prev;

        /**后继节点**/
        volatile Node next;

        /**节点对应的线程**/
        volatile Thread thread;

        /**等待队列中的后继节点**/
        Node nextWaiter;

        Node() {
        }

        /**addWaiter 会调用此函数**/
        Node(Thread thread, Node mode){
            this.thread = thread;
            this.nextWaiter = mode;
        }

        /**Condition 会调用此函数**/
        Node(Thread thread, int waitStatus) {
            this.waitStatus = waitStatus;
            this.thread = thread;
        }
    }

    private transient volatile  Node head;

    private transient volatile Node tail;

    private volatile int state;

    /**
     * 获取锁状态
     * @return
     */
    protected final int getState(){
        return state;
    }

    /**
     * 设置锁状态
     * @param newState
     */
    protected final void setState(int newState){
        state = newState;
    }

    /**
     * 尝试获取锁
     * @param arg
     * @return
     */
    protected boolean tryAcquire(int arg) {
        throw new UnsupportedOperationException();
    }

    /**
     * 尝试释放锁
     * @param arg
     * @return
     */
    protected boolean tryRelease(int arg) {
        throw new UnsupportedOperationException();
    }

    /**
     * 通过循环+CAS在队列中成功插入一个节点并且返回
     * @param node
     * @return
     */
    private Node enq(final Node node) {
        for(;;){
            Node t = tail;
            //初始化head和tail
            if(t == null){
                if(compareAndSetHead(node))
                    tail = head;
            } else {
                /**
                 *AQS精妙之处在与很多细节代码
                 * 比如需要用CAS往对位增加一个元素 此处的else分支是先在CAS的if前设置node.prev = t,而不是在CAS成功之后在设置
                 * 一方面是基于CAS的双向链表插入目前没有完美的解决方案，另一方面这样做的好处是：
                 * 保证每时每刻node.prev 都不会是一个null值 如果node.prev = t 放在下面if的里面 会导致一个瞬间 node.prev = null;这样会使队列不完整
                 */
                node.prev = t;
                //CAS设置tail为node,成功后把老的tail也就是t链接到node
                if(compareAndSetTail(t,node)){
                    log.info("第二次添加到阻塞队列队尾的线程是"+Thread.currentThread().getName());
                    t.next = node;
                    return t;
                }
            }
        }
    }


    /**
     * 在队列中新增一个节点
     * @param mode
     * @return
     */
    private Node addWaiter(Node mode) {
        Node node = new Node(Thread.currentThread(), mode);
        Node pred = tail;
        //快速尝试
        if(pred != null){
            node.prev = pred;
            //通过CAS在队尾插入当前节点
            if(compareAndSetTail(pred, node)){
                log.info("快速尝试添加到阻塞队列队尾的线程是"+Thread.currentThread().getName());
                pred.next = node;
                return node;
            }
        }
        //初始情况或者在快速尝试失败后自旋插入节点
        enq(node);
        return node;
    }

    /**
     * 设置当前node为head节点
     * @param node
     */
    private void setHead(Node node) {
        head = node;
        node.thread = null;
        node.prev = null;
    }

    /**
     * 唤醒后继线程
     * @param node
     */
    private void unparkSuccessor(Node node) {
        int ws = node.waitStatus;
        if(ws < 0)
            compareAndSetWaitStatus(node, ws, 0);

        Node s = node.next;
        if(s == null || s.waitStatus >0){
            s = null;
            for(Node t = tail; t != null && t != node; t = t.prev)
                if(t.waitStatus <= 0 )
                    s = t;
        }
        if(s != null)
            LockSupport.unpark(s.thread);
    }

    /**
     * 该方法实现某个node取消获取锁
     * @param node
     */
    private void cancelAcquire(Node node) {
        if(node == null)
            return;

        node.thread = null;

        Node pred = node.prev;
        while (pred.waitStatus > 0)
            node.prev = pred = pred.prev;

        Node predNext = pred.next;

        node.waitStatus = Node.CANCELLED;

        if(node == tail && compareAndSetTail(node,pred)){
            compareAndSetNext(pred, predNext,null);
        } else {
            int ws;
            if(pred != head &&
                    ((ws = pred.waitStatus) == Node.SIGNAL ||
                    (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
            pred.thread != null) {
                Node next = node.next;
                if (next != null && next.waitStatus <= 0)
                    compareAndSetNext(pred, predNext, next);
            } else {
                unparkSuccessor(node);
            }

            node.next = node;
        }

    }

    /**
     * 根据前驱节点的中的waitStatus来判断是否要阻塞当前线程
     * @param pred
     * @param node
     * @return
     */
    private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
        int ws = pred.waitStatus;
        if(ws == Node.SIGNAL)
        /**
         * 前驱节点设置为SIGNAL状态 在释放锁的时候会唤醒后继节点
         * 所以后继节点（也就是当前线程）现在可以阻塞自己
         */
            return true;
        if(ws > 0){
            /**
             * 前驱节点状态为取消，向前遍历 更新当前节点的前驱节点为往前一个非取消节点
             * 当前线程之后会再次回到循环并尝试获得锁
             */
            do{
                node.prev = pred = pred.prev;
            }while (pred.waitStatus > 0);
            pred.next = node;
        } else {
            /**
             * 等待状态为0或者PROPAGATE(-3),设置前驱节点的状态为SIGANAL
             * 并且之后会回到循环再次重试获得锁
             */
            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }
        return false;
    }


    /**
     * 中断当前线程
     */
    static void selfInterrupt() {
        Thread.currentThread().interrupt();
    }

    /**
     * 阻塞当前线程 并在阻塞过程中是否有其他线程中断该线程 返回中断状态
     * @return
     */
    private final boolean parkAndCheckInterrupt() {
        log.info("当前被阻塞的线程是"+Thread.currentThread().getName());
        LockSupport.park(this);
        return Thread.interrupted();
    }

    /**
     * 在队列的节点通过此方法获得锁
     * @param node
     * @param arg
     * @return
     */
    final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interruped = false;
            for(;;){
                final Node p = node.prev;
                /**
                 * 检测当前节点是否为head 这是尝试获取锁的资格
                 * 如果是的话 则调用tryAcquire尝试获得锁 成功则将head设置为当前节点
                 */
                if(p == head && tryAcquire(arg)){
                    setHead(node);
                    p.next = null;
                    failed = false;
                    return interruped;
                }
                /**
                 * 如果未成功获得锁，则根据前驱节点判断是否要阻塞
                 * 如果阻塞过程中被中断 者设置interruped标识未true
                 * shouldParkAfterFailedAcquire方法在前驱节点不为SINGNAL的情况下都会循环重试获取锁
                 */
                if(shouldParkAfterFailedAcquire(p, node) &&
                   parkAndCheckInterrupt())
                    interruped = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }

    }

    protected boolean isHeldExclusively() {
        throw new UnsupportedOperationException();
    }

    /**
     * 首先尝试获取一次锁 如果成功 则返回；
     * 否则会把当前线程包装成Node节点插入到队列中 在队列中判断是否为head的直接后继节点 并尝试获取锁
     * 如果获取失败 则阻塞当前线程 直至被 “释放锁的线程” 唤醒或者被中断 随后再次尝试获取锁 如此反复
     * @param arg 抢占锁的数量
     */
    public final void acquire(int arg){
        if(!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE),arg))
            selfInterrupt();
    }

    public final boolean release(int arg) {
        if(tryRelease(arg)) {
            Node h = head;
            if(h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            log.info("当前释放的是"+Thread.currentThread().getName());
            return true;
        }
        return false;
    }

    /**
     * 判断node　是否在sync Queue里面
     * @param node　
     * @return
     */

    final boolean isOnSyncQueue(Node node) {
        /**
         *  node.waitStatus == Node.CONDITION 则说明Node 一定在 Condition 里面
         *  node.prev == null 说明node 一定不在Sync Queue  里面（prev指针只有在CCLH(FIFO)队列中的节点有，尾插法保证prev指针一定不为空）
         */
        if(node.waitStatus == Node.CONDITION || node.prev == null)
            return false;
        //node.next != null 一定在Sync Queue 里面（next的指针只有在Sync Queue 节点才有，Condition Queue 的节点是nextWaiter） 但是反过来Sync Queue 里面的 节点不一定 node.next != null
        if(node.next != null)
            return true;
        //如果上面的方法无法快速判断的话，就只能从Sync Queue 里面去遍历，一个一个的判断了
        return findNodeFromTail(node);
    }

    /**
     * 从tail 开始查找 node 是否在Sync Queue中
     * @param node
     * @return
     */
    private boolean findNodeFromTail(Node node) {
        Node t = tail;
        for (;;){
            if(t == node)
                return true;
            if(t == null)
                return false;
            t = node.prev;
        }
    }

    /**
     * 将node 从 Condition Queue  转移到 Sync Queue 里面
     * 在调用transferForSignal
     * @param node
     * @return
     */
    final boolean transferForSignal(Node node) {
        //若 node 不是CONDITION状态 则失败 跳过当前节点 相当于把当前节点踢出Condition Queue
        if(!compareAndSetWaitStatus(node, Node.CONDITION, 0))
            return false;

        //加入Sync Queue
        Node p = enq(node);
        int ws = p.waitStatus;
        //这里的 ws > 0 指Sync Queue 中node 的前继节点cancelled 了 所以 唤醒一下node
        //compareAndSetWaitStatus(p, ws, Node.SIGNAL)失败 则说明 前继节点已经变成了SIGNAL 或 cancelled 所以也要唤醒
        if(ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
            LockSupport.unpark(node.thread);
        return true;
    }


    /**
     *将 Condition Queue  中因 timeout/interrupt 而唤醒的节点进行转移
     * @param node
     * @return
     */
    final boolean transferAfterCancelledWait(Node node) {
        //判断当前节点是否是CONDITION
        if(compareAndSetWaitStatus(node, Node.CONDITION, 0)){
            //如果抢占成功了就表示当前节点是CONDITION状态 此刻就意味着interruptMode为THROW_IE
            //进入队列 随后进行抢占锁的操作
            enq(node);
            return true;
        }

        //这时是其他线程发送signal 将本线程 转移到Sync Queue 里面的过程中（转移的过程中 waitStatus = 0了 所以上面的CA操作失败）
        //这里调用isOnSyncQueue判断是否已经进入Sync Queue 了
        while (!isOnSyncQueue(node))
            Thread.yield();
        return false;
    }


    /**
     *如果当前线程存在多次重入 那么这个方法只需要释放一次 就可以吧所以的重入次数归零
     * @param node
     * @return
     */
    final int fullyRelease(Node node) {
        boolean failed = true;
        try {
            //获得重入的次数
            int savedState = getState();
            //释放锁并且唤醒下一个同步队列中的线程
            if(release(savedState)) {
                failed = false;
                return savedState;
            }else {
                throw new IllegalMonitorStateException();
            }
        }finally {
            if(failed)
                node.waitStatus = Node.CANCELLED;
        }
    }


    protected final boolean compareAndSetState(int expect, int update){
        return unsafe.compareAndSwapInt(this,stateOffset,expect,update);
    }

    public  class LSPConditionObject implements LSPCondition, Serializable{

        private transient Node firstWaiter;

        private transient Node lastWaiter;

        /**
         * 下面两个用于追踪 调用 await 方法有没有被中断过
         * 主要区别是
         *  REINTERRUPT: 代表线程是在signal 后被中断的 (REINTERRUPT = re - interrupt 再次中断 最后会调用selfInterrupt)
         *  THROW_IE： 代表线程是在signal 前被中断的 则直接抛出异常（Throw_IE = throw inner exception）
         */
        /**在离开 awaitXX 方法 因为在接受 signal 前被中断 所以需要抛出异常 **/
        private static final int THROW_IE = -1 ;
        /**在离开 awaitXX 方法 退出前再次 自我中断（调用selfInterrupt）**/
        private static final int REINTERRUPT = 1;

        public LSPConditionObject() { }


        /**
         * 将当前线程封装成一个Node节点 放入 Condition Queue 里面
         * 下面对Condition Queue 的操作没有考虑到并发（Sync Queue 的队列是支持并发操作的），因为在进行操作时 Condition是当前线程 已经获取到了AQS的独占锁，所以不需要考虑并发的情况
         * @return
         */
        private   Node addConditionWaiter(){
            //Condition queue队列的尾节点
            Node t = lastWaiter;
            //尾节点已经Cancel 直接进行删除
            //t.waitStatus != Node.CONDITION -> 在对线程进行中断时
            // ConditionObject -> await -> checkInterruptWhileWaiting -> transferAfterCancelledWait "compareAndSetWaitStatus(node, Node.CONDITION, 0 )"
            //导致这种情况一般时线程中断或者 await 超时
            //当Condition 进行 wait 超时或被中断时 ， Condition里面的节点是没有被删除掉的，
            //需要其他 await 在将线程加入Condition queue 时调用 addConditionWaiter而进行删除，或await操作差不多结束时 调用 “node.nextWaiter != null ” 进行判断而进行删除
            //（ps: 通过signal 进行唤醒时 node.nextWaiter 会被置空，而中断和超时不会）
            if(t != null && t.waitStatus != Node.CONDITION){
                //调用unlinkCancelledWaiters对 “waitStatus != Node.CONDITION” 的节点进行删除 （在Condition 里面Node的waitStatus,要么是CONDITION(正常) 要么就是 0 （signal/timeout/interrupt））
                unlinkCancelledWaiters();
                //获取最新的lastWaiter
                t = lastWaiter;
            }
            //将线程封装成 Node ，准备放入Condition Queue 队列里面
            Node node = new Node(Thread.currentThread(), Node.CONDITION);
            if(t == null)
                //如果Condition Queue 是空的
                firstWaiter = node;
            else
                //追加到queue尾部
                t.nextWaiter = node;
            //从新赋值lastWaiter
            lastWaiter = node;
            return node;
        }

        /**
         * 唤醒 Condition Queue 里面的头节点 注意这里只是将 Node 从 Condition Queue 转移到Sync Queue 里面（这时的 Node 还是可以被Interrupt）
         * @param first
         */
        private void doSignal(Node first) {
          do{
              //将 first.nextWaiter 赋值给 nextWaiter 为下次做准备
              if((firstWaiter = first.nextWaiter) == null)
                  //这时若 nextWaiter == null;则说明 Condition 为空了 则说明Condition空了 所以直接置空 lastWaiter
                  lastWaiter = null;
              //。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
              first.nextWaiter = null;
              //调用 transferForSignal 将 first 转移到Sync Queue 里面 ，返回成功的话，将firstWaiter 赋值给first
          }while ( !transferForSignal(first) &&
                  (first = firstWaiter) != null);
        }

        /**
         * 在调用 addConditionWaiter 将线程放入 Condition Queue 里面时 或await 方法获取差不多结束时 进行清理 Condition Queue 里面的因 timeout/interrupt 而还存在的节点
         * 这个删除比较巧妙 其中引入了trail 节点 可以理解为 traverse整个 Condition Queue 时遇到的最后一个有效的节点
         */
        private void unlinkCancelledWaiters() {
            Node t = firstWaiter;
            Node trail = null;
            while (t != null){
                //先初始化next节点
                Node next = t.nextWaiter;
                //节点状态无效 在Condition Queue里面 Node.waitStatus 只有可能 Condition 或者是 0（timeout/interrupt）引起的
                if(t.waitStatus != Node.CONDITION){
                    // Node.nextWaiter 置空
                    t.nextWaiter = null;
                    //一直都没有遇到有效的节点
                    if(trail == null)
                        //将next 赋值给 firstWaiter(此时next 可能也是无效的，这里只是一个临时处理)
                        firstWaiter = next;
                    else
                        //将next 赋值给  trail.nextWaiter 这一步其实就是删除节点
                        trail.nextWaiter = next;
                    //next == null 说明已经traverse 完了 Condition Queue
                    if(next == null)
                        lastWaiter = trail;
                }
                else
                    //将有效节点赋值给trail
                    trail= t;
                t = next;
            }
        }

        /**
         * 将 Condition Queue 的头节点转移到 Sync Queue 里面
         * 在进行调用 signal 时 当前线程必须获取到了独占锁
         */
        public final void signal() {
            //判断当前线程是否已经获取  独占锁
            if(!isHeldExclusively())
                throw new IllegalMonitorStateException();
            Node first = firstWaiter;
            if(first != null)
                //调用 doSignal 进行转移
                doSignal(first);
        }

        /**
         *检查 在 await方法中 的这次唤醒 是否是中断引起的
         * 若是中断引起的 则将 Node 从 Condition Queue 转移到 Sync Queue
         * 返回值的区别：
         *            0： 此时唤醒是通过signal -> LockSupport.unpark
         *            THROW_IE: 此时唤醒是通过 interrupt 并且在接受 signal 之前
         *            REINTERRUPT： 线程的唤醒是通过 signal  而后又被中断
         * @param node
         * @return
         */
        private int checkInterruptWhileWaiting(Node node) {
            return Thread.interrupted() ?
                    (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
                    0;
        }

        /**
         * 这个方法是 awaitXX  方法离开前调用的 ，主要是根据
         * interrupMode 判断是抛出异常 还是在自我中断一下
         * @param interruptMode
         * @throws InterruptedException
         */
        private void reportInterruptAfterWait(int interruptMode) throws InterruptedException {
            if(interruptMode == THROW_IE)
                throw new InterruptedException();
            else if(interruptMode == REINTERRUPT)
                selfInterrupt();
        }

        /**
         * 支持 InterruptException 的 await <- 注意这里即使线程被中断
         * 还是需要获取独占的锁后 在调用 lock.unlock 进行释放锁
         * @throws InterruptedException
         */
        @Override
        public void await() throws InterruptedException {
            //判断是否中断
            if(Thread.interrupted())
                throw new InterruptedException();
            //将线程封装成一个 Node 放到 Condition Queue 里面 其中可能有些清理工作
            Node node = addConditionWaiter();
            //释放当钱线程获取的所有锁（ps： 调用await 方法时 当前线程必须是已经获取到了独占的锁）
            int savedState = fullyRelease(node);
            int interruptMode = 0;
            //判断当前线程是否在 Sync Queue 里面（这里的Node 从 Condition Queue  里面 转移到 Sync Queue 里面有两种可能 （1） 其他线程调用signal 进行转移 （2） 当前线程被中断而进行Node的转移（就在checkInterruptWhileWaiting）里面进行转移）
            while (!isOnSyncQueue(node)){
                //当前线程没有在Condition Queue 里面 ，则进行block
                LockSupport.park(this);
                //判断线程是否因为中断被唤醒，若是中断则会在checkInterruptWhileWaiting的transferAfterCancelledWait 进行节点转移 返回值interruptMode != 0
                if((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    //说明此是通过线程中断而唤醒，并且已经进行了节点的转移。转移到Sync Queue 里面
                    break;
            }
            //调用acquireQueued 在 Sync Queue 里面进行 独占锁的获取 返回值表明在获取的过程中没有被中断过
            if(acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            //通过node.nextWaiter != null 判断 线程的唤醒是中断还是signal,因为通过中断唤醒的话，此刻代表线程的Node 在Condition Queue 与 Sync Queue 都会存在
            if(node.nextWaiter != null)
                //进行cancelled 节点的删除
                unlinkCancelledWaiters();
            //interruptMode != 0  代表通过线程中断的方式唤醒线程
            if(interruptMode != 0)
                //根据interruptMode 的类型决定是抛出异常 还是自己在中断一下
                reportInterruptAfterWait(interruptMode);
        }
    }



    //在使用该getUnsafe方法是，会判断classLoader的类型，如果不是systemClassLoader则会抛出SecurityException(“Unsafe”)异常(jdk 12可以直接获取)
    //private static final Unsafe unsafe = Unsafe.getUnsafe();
    //通过反射获取
    private static final  Unsafe unsafe = reflectGetUnsafe();
    private static final long stateOffset;
    private static final long headOffset;
    private static final long tailOffset;
    private static final long waitStatusOffset;
    private static final long nextOffset;

    public static Unsafe reflectGetUnsafe() {
        try {
            Field field = Unsafe.class.getDeclaredField("theUnsafe");
            field.setAccessible(true);
            return (Unsafe) field.get(null);
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }

    static {
        try {
            stateOffset = unsafe.objectFieldOffset
                    (AbstractQueuedSynchronizer.class.getDeclaredField("state"));
            headOffset = unsafe.objectFieldOffset
                    (AbstractQueuedSynchronizer.class.getDeclaredField("head"));
            tailOffset = unsafe.objectFieldOffset
                    (AbstractQueuedSynchronizer.class.getDeclaredField("tail"));
            waitStatusOffset = unsafe.objectFieldOffset
                    (Node.class.getDeclaredField("waitStatus"));
            nextOffset = unsafe.objectFieldOffset
                    (Node.class.getDeclaredField("next"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private final boolean compareAndSetHead(Node update) {
        return unsafe.compareAndSwapObject(this, headOffset, null, update);
    }

    private final boolean compareAndSetTail(Node expect, Node update) {
        return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
    }

    private static final boolean compareAndSetWaitStatus(Node node,
                                                         int expect,
                                                         int update) {
        return unsafe.compareAndSwapInt(node, waitStatusOffset,
                expect, update);
    }

    private static final boolean compareAndSetNext( Node node,
                                                    Node expect,
                                                    Node update) {
        return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
    }

}
